package 开始的算法算法入门8月.链表;
// https://leetcode-cn.com/problems/reverse-linked-list/submissions/
public class 反转链表2060821 {


      public class ListNode {
          int val;
          ListNode next;
          ListNode() {}
          ListNode(int val) { this.val = val; }
          ListNode(int val, ListNode next) { this.val = val; this.next = next; }
      }

    class Solution {
        //迭代方法
        // public ListNode reverseList(ListNode head) {
        //    ListNode prev=null,next;
        //    ListNode curr=head;
        //    while(curr!=null){
        //        next=curr.next;
        //        curr.next=prev;
        //        prev=curr;
        //        curr=next;
        //    }
        //    return prev;
        // }
        //递归
        public ListNode reverseList(ListNode head) {

            if(head==null||head.next==null){
                return head;
            }
            ListNode p=reverseList(head.next);
            head.next.next=head;
            head.next=null;
            return p;
        }
    }
/*
假设链表为1→2→3→∅，我们想要把它改成  ∅←1←2←3。
在遍历链表时，将当前节点的next 指针改为指向前一个节点。
由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。
在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
*/
}
